/*
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 *    CosineDistance.java
 *    Copyright (C) 2012 Rodders and Andy
 *
 */

package weka.core;  

import weka.core.TechnicalInformation.Field;
import weka.core.TechnicalInformation.Type;
import weka.core.converters.ConverterUtils.DataSource;
import weka.core.neighboursearch.PerformanceStats;



/**
 <!-- globalinfo-start -->
 * Implementing Cosine distance (or similarity) function.<br/>
 * <br/>
 * One object defines not one distance but the data model in which the distances between objects of that data model can be computed.<br/>
 * <br/>
 * Attention: For efficiency reasons the use of consistency checks (like are the data models of the two instances exactly the same), is low.<br/>
 * <br/>
 * For more information, see:<br/>
 * <br/>
 * Wikipedia. Cosine distance. URL http://en.wikipedia.org/wiki/Cosine_similarity.
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- technical-bibtex-start -->
 * BibTeX:
 * <pre>
 * &#64;misc{missing_id,
 *    author = {Wikipedia},
 *    title = {Cosinexx distance},
 *    URL = {http://en.wikipedia.org/wiki/Cosine_similarity}
 * }
 * </pre>
 * <p/>
 <!-- technical-bibtex-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -D
 *  Turns off the normalization of attribute 
 *  values in distance calculation.</pre>
 * 
 * <pre> -R &lt;col1,col2-col4,...&gt;
 *  Specifies list of columns to used in the calculation of the 
 *  distance. 'first' and 'last' are valid indices.
 *  (default: first-last)</pre>
 * 
 * <pre> -V
 *  Invert matching sense of column indices.</pre>
 * 
 <!-- options-end --> 
 *
 * @author Rodders 
 * @author Andy
 * 
 * @version $Revision: 8034 $
 */
public class CosineDistanceRM
  extends NormalizableDistance
  implements Cloneable, TechnicalInformationHandler {

  /** for serialization. */
  private static final long serialVersionUID = 1068606253458807903L;

  /**
   * Constructs an Cosine Distance object, Instances must be still set.
   */
  public CosineDistanceRM() {
    super();
  }

  /**
   * Constructs an Cosine Distance object and automatically initializes the
   * ranges.
   * 
   * @param data 	the instances the distance function should work on
   */
  public CosineDistanceRM(Instances data) {
    super(data);
  }

  /**
   * Returns a string describing this object.
   * 
   * @return 		a description of the evaluator suitable for
   * 			displaying in the explorer/experimenter gui
   */
  public String globalInfo() {
    return 
        "Implementing Cosine distance (or similarity) function.\n\n"
      + "One object defines not one distance but the data model in which "
      + "the distances between objects of that data model can be computed.\n\n"
      + "Attention: For efficiency reasons the use of consistency checks "
      + "(like are the data models of the two instances exactly the same), "
      + "is low.\n\n"
      + "For more information, see:\n\n"
      + getTechnicalInformation().toString();
  }

  /**
   * Returns an instance of a TechnicalInformation object, containing 
   * detailed information about the technical background of this class,
   * e.g., paper reference or book this class is based on.
   * 
   * @return 		the technical information about this class
   */
  public TechnicalInformation getTechnicalInformation() {
    TechnicalInformation 	result;
    
    result = new TechnicalInformation(Type.MISC);
    result.setValue(Field.AUTHOR, "Wikipedia");
    result.setValue(Field.TITLE, "Cosine distance");
    result.setValue(Field.URL, "http://en.wikipedia.org/wiki/Cosine_similarity");

    return result;
  }
  
  /**
   * Calculates the distance between two instances.
   * 
   * @param first 	the first instance
   * @param second 	the second instance
   * @return 		the distance between the two given instances
   */
  public double distance(Instance first, Instance second) {
	  /** RM 1SEP2012 
	   * Refers to a distance argument with an extra third argument, a cut-off
	   * value at which point the distance calculation aborts.
	   */
    return distance(first, second, Double.POSITIVE_INFINITY);
  }
  
  /**
   * Calculates the distance (or similarity) between two instances. Need to
   * pass this returned distance later on to postprocess method to set it on
   * correct scale. <br/>
   * P.S.: Please don't mix the use of this function with
   * distance(Instance first, Instance second), as that already does post
   * processing. Please consider passing Double.POSITIVE_INFINITY as the cutOffValue to
   * this function and then later on do the post processing on all the
   * distances.
   *
   * @param first 	the first instance
   * @param second 	the second instance
   * @param stats 	the structure for storing performance statistics.
   * @return 		the distance between the two given instances or 
   * 			Double.POSITIVE_INFINITY.
   */
  public double distance(Instance first, Instance second, PerformanceStats stats) { //debug method pls remove after use
	  /** RM 1SEP2012 
	   * Refers to a distance argument with an extra third argument, a cut-off
	   * value at which point the distance calculation aborts.
	   * NOTE that this distance method is intended as a debug method.
	   * NOTE TOO THAT THE METHOD WITH FOUR ARGUMENTS IS INHERITED FROM THE 
	   * SUPERCLASS NormalizableDistance.
	   */
	  return distance(first, second, Double.POSITIVE_INFINITY, stats);
  }
  

  /**
   * RM 1SEP2012
   * COPIED FROM THE SUPERCLASS NormalizableDistance.
   * Calculates the distance between two instances. Offers speed up (if the 
   * distance function class in use supports it) in nearest neighbour search by 
   * taking into account the cutOff or maximum distance. Depending on the 
   * distance function class, post processing of the distances by 
   * postProcessDistances(double []) may be required if this function is used.
   *
   * @param first 	the first instance
   * @param second 	the second instance
   * @param cutOffValue If the distance being calculated becomes larger than 
   *                    cutOffValue then the rest of the calculation is 
   *                    discarded.
   * @param stats 	the performance stats object
   * @return 		the distance between the two given instances or 
   * 			Double.POSITIVE_INFINITY if the distance being 
   * 			calculated becomes larger than cutOffValue. 
   */
  public double distance(Instance first, Instance second, double cutOffValue, PerformanceStats stats) {
	    
	double dotProduct = 0;
	double firstInstanceSize = 0, secondInstanceSize = 0;
    double distance = 0;
	
    int firstI, secondI;
    int firstNumValues = first.numValues();
    int secondNumValues = second.numValues();
    int numAttributes = m_Data.numAttributes();
    int classIndex = m_Data.classIndex();
    
    /** RM 1SEP2012 I think we need to include this initialization from the
     *  superclass.
     */
    validate();
    
    for (int p1 = 0, p2 = 0; p1 < firstNumValues || p2 < secondNumValues; ) {
      if (p1 >= firstNumValues)
    	  firstI = numAttributes;
      else
    	  firstI = first.index(p1); 

      if (p2 >= secondNumValues)
    	  secondI = numAttributes;
      else
    	  secondI = second.index(p2);

      if (firstI == classIndex) {
    	  p1++; 
    	  continue;
      }
      
      /** RM 1SEP2012 NOTED OUT BY Tom. DON'T KNOW WHY **/
      if ((firstI < numAttributes) && !m_ActiveIndices[firstI]) {
    	  p1++; 
    	  continue;
      }
       
      if (secondI == classIndex) {
    	  p2++; 
    	  continue;
      }
      
      /** RM 1SEP2012 NOTED OUT BY Tom. DON'T KNOW WHY **/
      if ((secondI < numAttributes) && !m_ActiveIndices[secondI]) {
    	  p2++;
    	  continue;
      }
       
      double attributeProduct;
      double firstInstanceAttributeValue, secondInstanceAttributeValue;
      
      /** RM 1SEP2012 TO CHECK: That the new function product needs these three
       *  cases and no more and no less.
       **/
      if (firstI == secondI) {
    	  attributeProduct = product(firstI, replaceNaN(first.valueSparse(p1)), replaceNaN(second.valueSparse(p2)));
    	  firstInstanceAttributeValue = replaceNaN(first.valueSparse(p1));
    	  secondInstanceAttributeValue = replaceNaN(second.valueSparse(p2));
	
    	  p1++;
    	  p2++;
      }
      else if (firstI > secondI) {
    	  attributeProduct = product(secondI,0, replaceNaN(second.valueSparse(p2))); 
    	  firstInstanceAttributeValue = 0;
    	  secondInstanceAttributeValue = replaceNaN(second.valueSparse(p2));
    	  p2++;
      }
      else {
    	  attributeProduct = product(firstI,replaceNaN(first.valueSparse(p1)), 0);
    	  firstInstanceAttributeValue = replaceNaN(first.valueSparse(p1));
    	  secondInstanceAttributeValue = 0;
    	  p1++;
      }
           
      if (stats != null)
    	  stats.incrCoordCount();
      
      dotProduct = updateDotProduct(dotProduct, attributeProduct);
      firstInstanceSize = updateInstanceSize(firstInstanceSize, firstInstanceAttributeValue);
      secondInstanceSize = updateInstanceSize(secondInstanceSize, secondInstanceAttributeValue);
      if (dotProduct > cutOffValue || firstInstanceSize > cutOffValue || secondInstanceSize > cutOffValue)
        return Double.POSITIVE_INFINITY;
      
    }// end loop
    
    // java has problems with rounding errors :(
    if (firstInstanceSize == secondInstanceSize){
    	distance = 0;//1 - (dotProduct / firstInstanceSize);
    } else {
    	distance = Math.abs(1 - (dotProduct / (Math.sqrt(firstInstanceSize) * Math.sqrt(secondInstanceSize))));
    }
    if (Double.compare(distance, Double.NaN) == 0) {
    	distance = 1;
    };
    return distance;
  }
  
  /**
   * Returns 0 if the value passed is a NaN
   * in our context a NaN is a representation of the least similarity
   * 
   * @param double 
   * @return double 
   */
  private double replaceNaN(double in){
	  if (Double.compare(in, Double.NaN) == 0) {
	    	return 0;
	    }
	  return in;
  }
  
  
  /**
   * Returns the product of two values of an attribute.
   * 
   * @param index	the attribute index
   * @param value1	the first value
   * @param value2	the second value
   * @return		the product
   */
  protected double product(int index, double value1, double value2) {
	  switch(m_Data.attribute(index).type()) {
	  case Attribute.NOMINAL:
		  return 0;
	  case Attribute.NUMERIC:
		  return value1 * value2;
	  }
	  /**
	   * RM 5SEP2012 It is OK to return Double.NaN when a difference is being
	   * taken of that value and the same value but not when the two values are
	   * being multiplied instead of subtracted. To ignore non-numerical values
	   * in the dot product, they need to be returned as zero.
	   */
	  return 0;
  }
  
  /**
   * Updates the current instance size calculated so far with the new attribute
   * value.
   * 
   * @param currentInstanceSize	the current instance size calculated so far
   * @param newAttributeValue	the value of the new attribute
   * @return		the updated instance size
   * @see		#difference(int, double, double)
   */
  protected double updateInstanceSize(double currentInstanceSize, double newAttributeValue) {
    double	result;
    
    result  = currentInstanceSize;
    result += newAttributeValue * newAttributeValue;
    
    return result;
  }
  
  
  
  /**
   * Updates the current dot product calculated so far with the new product of
   * two attributes. The product of the attributes was calculated with the
   * product(int,double,double) method.
   * 
   * @param currentDotProduct	the current dot product calculated so far
   * @param newProduct      	the product of the two new attribute values
   * @return		            the updated dot product
   * @see		                #product(int, double, double)
   */
  protected double updateDotProduct(double currentDotProduct, double newProduct) {
    double	result;
    
    result  = currentDotProduct;
    result += newProduct;
    
    return result;
  }
  
  /**
   * This method is not needed but it has to be included, 
   * the method signature in the ancestor is abstract.
   * Updates the current distance calculated so far with the new difference
   * between two attributes. The difference between the attributes was 
   * calculated with the difference(int,double,double) method.
   * 
   * @param currDist	the current distance calculated so far
   * @param diff	the difference between two new attributes
   * @return		the update distance
   * @see		#difference(int, double, double)
   */
  protected double updateDistance(double currDist, double diff) {
    return Double.NaN;
  }
  
  /**
   * Does post processing of the distances (if necessary) returned by
   * distance(distance(Instance first, Instance second, double cutOffValue). It
   * is necessary to do so to get the correct distances if
   * distance(distance(Instance first, Instance second, double cutOffValue) is
   * used. This is because that function actually returns the squared distance
   * to avoid inaccuracies arising from floating point comparison.
   * 
   * @param distances	the distances to post-process
   */
  public void postProcessDistances(double distances[]) {
    
  }
  


  /**
   * Returns the index of the closest point to the current instance.
   * Index is index in Instances object that is the second parameter.
   *
   * @param instance 	the instance to assign a cluster to
   * @param allPoints 	all points
   * @param pointList 	the list of points
   * @return 		the index of the closest point
   * @throws Exception	if something goes wrong
   */
  public int closestPoint(Instance instance, Instances allPoints,
      			  int[] pointList) throws Exception {
    double minDist = Integer.MAX_VALUE;
    int bestPoint = 0;
    for (int i = 0; i < pointList.length; i++) {
      double dist = distance(instance, allPoints.instance(pointList[i]), Double.POSITIVE_INFINITY);
      if (dist < minDist) {
        minDist = dist;
        bestPoint = i;
      }
    }
    return pointList[bestPoint];
  }
  
  /**
   * Returns true if the value of the given dimension is smaller or equal the
   * value to be compared with.
   * 
   * @param instance 	the instance where the value should be taken of
   * @param dim 	the dimension of the value
   * @param value 	the value to compare with
   * @return 		true if value of instance is smaller or equal value
   */
  public boolean valueIsSmallerEqual(Instance instance, int dim,
      				     double value) {  //This stays
    return instance.value(dim) <= value;
  }
  
  /**
   * Returns the revision string.
   * 
   * @return		the revision
   */
  public String getRevision() {
    return RevisionUtils.extract("$Revision: 8034 $");
  }
  
  public static void main(String[] args) throws Exception {
	  // sample 4 - triangles 3 -missing values 2 general test sample large numbers
	  String src = "sample2.csv";
	  DataSource source = new DataSource(src);
	  Instances data = source.getDataSet();
	  
	  CosineDistanceRM cd = new CosineDistanceRM(data);
	  System.out.println(data.toString());
	  System.out.println("Instance 1: " + data.instance(0) + " Instance 2: " + data.instance(1) + " cosine distance: " + cd.distance(data.instance(0), data.instance(1)));
	  System.out.println("Instance 1: " + data.instance(2) + " Instance 2: " + data.instance(3) + " cosine distance: " + cd.distance(data.instance(2), data.instance(3)));
	  System.out.println("Instance 1: " + data.instance(4) + " Instance 2: " + data.instance(5) + " cosine distance: " + cd.distance(data.instance(4), data.instance(5)));
	  System.out.println("Instance 1: " + data.instance(6) + " Instance 2: " + data.instance(7) + " cosine distance: " + cd.distance(data.instance(6), data.instance(7)));
	  System.out.println("Instance 1: " + data.instance(8) + " Instance 2: " + data.instance(9) + " cosine distance: " + cd.distance(data.instance(8), data.instance(9)));	  
	  System.out.println("Instance 1: " + data.instance(10) + " Instance 2: " + data.instance(11) + " cosine distance: " + cd.distance(data.instance(10), data.instance(11)));
	  System.out.println("Instance 1: " + data.instance(12) + " Instance 2: " + data.instance(13) + " cosine distance: " + cd.distance(data.instance(12), data.instance(13)));
	  
  }
}
